\documentclass[a4paper, 11pt]{article}


\usepackage{geometry}
\usepackage[french]{babel}
\usepackage[utf8]{inputenc}
\usepackage[T1]{fontenc}
\usepackage{lmodern}


\geometry{margin=2.5cm}

\usepackage{fancyhdr}
\usepackage{fancyvrb} 
\usepackage{graphicx}
\usepackage{float}
%\usepackage{wrapfig}

\pagestyle{fancy}
\rhead{PMG}
\renewcommand{\footrulewidth}{0.5pt}



\begin{document}

\begin{titlepage}
  \begin{center}

    \textsc{\LARGE Rapport du projet de Programmation\\ Multic\oe ur et GPU}\\[2cm]
    \textsc{\Large Sylvain Vaglica\hspace{2cm} Stéphane Castelli}\\[3cm]
    \textsc{\large \today }\\[1.5cm]
    \includegraphics[width=8cm]{logo.jpg}

\end{center}

\end{titlepage}

\tableofcontents
\clearpage
\section{Introduction}
De plus en plus, avec l'apparition des processeurs multic\oe ur, les applications se doivent d'avoir une exécution parallèle. Ceci apporte potentiellement une réduction importante du temps de calcul, notamment dans le cas de calculs lourds appliqués de manière indépendante sur plusieurs données. Mais il existe un matériel possédant un nombre d'unités de calcul bien plus important que le processeur : il s'agit de la carte graphique. Auparavant réservée au calcul d'images, et l'on pense surtout aux jeux-vidéos, il est désormais possible de faire réaliser par celle-ci d'autres calculs, profitant ainsi d'une parallélisation massive de l'exécution de son code. Mais il n'est \emph{à priori} pas trivial d'utiliser la carte graphique pour cet  usage, d'où l'émergence de \emph{OpenCL}. Développé à l'origine par \emph{Apple}, il est devenu un standard ouvert soutenu par une majorité de constructeurs, et permet le \emph{GPGPU} (\emph{\textbf{G}eneral-Purpose \textbf{P}rocessing on \textbf{G}raphic \textbf{P}rocessing \textbf{U}nit}). Il combine un langage proche du \emph{C} et une \emph{API}, et autorise l'exécution sur la carte graphique (mais également une émulation sur le processeur) de portions de code, appelées \emph{kernel} (ou noyau).

Le but du projet est d'écrire en \emph{OpenCL} un code permettant de simuler des particules, par exemple les collisions entre elles. L'affichage à proprement parler se fait via \emph{OpenGL}, mais cette partie secondaire a été réalisée au préalable, il n'a donc pas été nécessaire de la coder. De même, l'initialisation de \emph{OpenCL} a été fournie, afin que l'effort soit concentré sur la réalisation des calculs sur le \emph{GPU}. Toute la difficulté réside dans l'adaptation d'algorithmes à une architecture vectorielle, et à l'optimisation en conséquence. Différents objectifs ont été fixés, tels que la gestion des collisions élastiques ou des bords ; chacun sera traité dans ce rapport.

\section{Mise en route}

\subsection{Analyse de l'existant}

Le programme fourni comme base de développement est déjà fonctionnel, et propose l'affichage des particules, les prototypes des fonctions à concrétiser pour répondre au cahier des charges, ainsi qu'un noyau d'exemple : \emph{eating}. Ce dernier donne l'illusion que les particules \og mangent\fg.
% screenshot
Ainsi, on a pu avoir un aperçu du paradigme sous-jacent à l'exécution sur carte graphique d'un code en \emph{OpenCL} : le développeur ne se charge pas de la parallélisation, tout est automatique. Il suffit de définir le nombre de \emph{threads} (ou \emph{work-item} dans la terminologie de \emph{openCL}), le code exécuté par chacun de ces threads, mais leur lancement ainsi que tous les détails techniques inhérents ne sont pas visibles. Il est tout de même important de savoir comment cela se passe en interne afin d'éviter de mauvaises surprises, et d'optimiser. En particulier, il importe de savoir que le \emph{GPU} est optimisé pour que un groupe de 32 \emph{threads} (appelé \emph{warp}), chez \emph{Nvidia} tout du moins,  exécute la même instruction sur une zone mémoire. Par conséquent, avoir un nombre de threads multiple de 16 (\emph{half warp})  améliore les temps d'accès mémoire (il faut également adapter la taille des tableaux, pour qu'un \emph{thread} n'accède pas à une zone mémoire interdite), de même que des noyaux faits de telle sorte que les \emph{threads} adjacents accèdent à des données adjacentes. En outre, cela nous a permis par exemple de voir comment identifier le thread dans lequel on se trouve, et de voir le processus nécessaire pour lancer un noyau.

\subsection{Un premier noyau}

La première tâche a consisté en la création d'un noyau déplaçant les atomes selon des vecteurs vitesse définis. Pour ce faire, on s'est inspiré du noyau donné en exemple. La difficulté était minime, le seul problème étant de déterminer l'indice correct dans le tableau des positions de la bonne coordonnée liée au bon atome, en fonction du \emph{thread} dans lequel on se trouve ; sans oublier que les tableaux, de vitesse et de position, consistent en une suite d'abscisses, quelques octets de décalage pour que l'ont ait un multiple de 16, suivis d'une suite d'ordonnées, de même quelques octets de décalage, puis une suite de profondeurs. 
% image du sujet sur les tableau, + légende détaillée

On peut constater que l'on utilise une grande quantité de \emph{threads}, un par sommet (les particules sont constituées de plusieurs sommets) le tout multiplié par la dimension, en l'occurrence trois. On peut avoir des doutes sur l'efficacité d'une telle méthode. Dans ce premier noyau, on lance en réalité autant de threads que de \emph{vertices} par atomes. Les \emph{vertices} sont en réalité les arêtes de chaque triangle, qui placés judicieusement dans l'espace, forment les sphères qui représentent les atomes. Plus il y a des triangles dans une sphère, plus la résolution est précise.
% ça serait bien de tester en faisant le calcul sur le processeur (ça ne devrait pas être trop difficile). Mais sinon, essayer de modifier le nombre de treads lancé, je pense qu'il n'y en a pas besoin d'autant (et faire les tests de perfs dans les deux cas)

\section{Implémentation de la simulation}

Pour la suite de ce projet, on ne fera plus attention aux sommets des particules, mais on définit une position et une vitesse unique pour toute la particule.
\subsection{Rebonds sur les parois}
La première tâche consiste à gérer les rebonds des particules sur les parois du cube. Les rebonds se font par symétrie par rapport au plan incident, et il est considéré qu'il n'y a pas de perte d'énergie au contact de la paroi --- l'évolution du système est thermodynamiquement réversible. Faire rebondir une particule revient donc à inverser une des composantes de sa vitesse, il sera donc vérifié à chaque itération et pour chacune d'entre elles si leur intersection avec une paroi est non-nulle, le cas échéant on inverse la composante adéquate de sa vitesse. Si l'on rentre en contact avec deux parois en même temps, on inverse les deux composantes. Si l'on est pas en contact avec une paroi, on ne fait rien.

Pour réaliser cette tâche, on crée autant de \emph{threads} que d'atomes (arrondi au multiple de 16 supérieur). Ainsi, chacun des \emph{thread} se charge de vérifier un atome, on utilise son indice afin de déterminer de quel atome on se charge. Le \emph{thread} $n$ se charge de l'atome $n$. Il n'est a priori pas possible de faire mieux.


\subsection{Collision entre particules - version simplifiée}
\subsubsection{Version 1}
On se charge à présent de gérer les collisions entre particules. Néanmoins, au lieu de faire repartir les particules dans la bonne direction, en fonction du modèle physique choisi, on enlève toute vitesse aux deux particules considérées : elles s'arrêtent. On lance donc, de manière naïve, autant de \emph{threads} qu'il y a d'atome. Chacun va vérifier que l'on n'est pas rentré en collision avec un autre atome. Afin de ne pas refaire deux fois le même calcul, on se contente vérifier par rapport aux atomes d'indice inférieur à celui du \emph{thread}. S'il y a collision, on met la vitesse des deux particules à 0. Toutefois, cette approche n'est pas optimale. En effet, le premier \emph{thread} n'a aucun calcul à faire, tandis que le dernier doit tout vérifier par rapport à toutes les autres particules. En conséquence, on imagine une deuxième version.
\subsubsection{Version 2}
Dans cette version, chaque \emph{thread} se charge de deux atomes : celui du même indice que celui du \emph{thread}, et son symétrique par rapport à la médiane: l'indice N-i, où N est le nombre d'atoms et i l'indice du \emph{thread} courant. De cette façon, chacun a autant de calculs à faire, et l'on améliore en théorie l'efficacité. Mais de manière générale, cette méthode n'est pas plus efficace que la première. En effet, on créer deux fois moins de \emph{threads} et chacun effectue en moyenne deux fois plus de travail que précédement. D'autre part, on notera que les accès à la mémoire sont disjoints, ce à quoi on tente de remédier dans la version suivante.
\subsubsection{Version3}
Dans cette dernière version, on n'améliore pas la complexité ou le nombre de calculs, mais l'on utilise le fait que les groupe de \emph{threads} partagent la même mémoire. Ainsi, il est possible d'utiliser cette mémoire en divisant drastiquement le nombre d'accès en mémoire. Nous n'avons malheureusement pas réussi à implémenter cette solution par manque de temps avant le débuts des stages. L'idée est de créer un \emph{thread} par atome, et de les grouper par 16. Chaque groupe va vérifier en même temps s'il y a collision avec les atomes d'indices $i + k * 16$   à $i + (k + 1) * 16$. Une fois cette phase terminée, on synchronise l'exécution des \emph{threads} grâce à une barrière, puis on incrémente $k$ et on recommence.
\subsection{Gravité}
La gravité est assez triviale à implémenter, il suffit d'appliquer une force constante à toutes les particules.

\subsection{Chocs élastiques entre particules}
Maintenant, au lieu d'arrêter les particules lorsqu'elles se rencontrent, on a va adopter le modèles des chocs élastiques. Les différentes méthodes possibles de parallélisation restent les mêmes que pour la collision simplifiée. Ce sont cependant les calculs qui sont plus difficiles. En effet, il convient d'effectuer un changement de repère pour exprimer les vitesses dans la base correcte. Cela relève plus de compétences mathématiques qu'informatiques. On remarquera cependant que la bibliothèque \emph{OpenCL} ne permet pas d'effectuer certaines opérations telles que le produit vectoriel, ou même le produit d'une matrice et d'un vecteur (application linéaire).
\subsection{Potentiel de Lennard Jones}
Le potentiel de Lennard Jones représente l'energie des forces s'exerçant entre deux atomes en fonction de la distance les séparant. Il faut à nouveau appliquer une force sur les atomes, mais dont la direction dépend de la position de chacun d'entre eux. il faut comme dans le cas de la collision, calculer les interactions entre tous le couples possibles d'atomes. Il faut dans ce cas là utiliser le même principe que dans la version 3 car chaque \emph{thread} est succeptible de modifier ET de lire la vitesse de tout les atomes. Pour la collision il n'y avait pas besoin de connaître la vitesse. L'utilisation des barrières est donc nécéssaire. Nous avons implémenté cette force sans l'utilisation des barrières, ce qui explique que nous ne visualisons pas un rendu symétrique lors de l'éxécution du programme sur le fichier \emph{immob.conf} qui représente trois atomes alignés.

\section{Conclusion}
Au travers de ces exemples d'application d'\emph{OpenCL}, on pu avoir un aperçu des capacités de ce langage, mais aussi des difficultés. En effet, avoir un programme fortement parallélisé n'implique pas forcément une grande performance, et ne vient pas nécessairement de manière immédiate. Par rapport à un programme séquentiel, il convient donc d'apporter une étape de réflexion supplémentaire, mais le gain peut également être très important. En particulier, dans le cas d'un grand nombre de particules, ce qu'on pourrait appeler un cas d'école, l'apport d'une déportation des calculs sur la carte graphique apparaît assez vite, car l'on applique un traitement unique sur un grand nombre de données. On parle dans ce cas de \emph{SIMD} : \emph{\textbf{S}ingle \textbf{I}nstruction, \textbf{M}ultiple \textbf{D}ata}. Sur un processeur classique, sans instructions dédiées à ce genre de calculs, il faudrait effectuer plusieurs milliers de fois le même calculs sur les données, à la suite. Ici, on réalise plusieurs calculs en même temps, et l'on divise d'autant le temps d'exécution. Sur du calcul en temps réel, ou du calcul lourd, c'est la seule façon de parvenir à ses fins. La carte graphique ne sert plus qu'à calculer du graphique, entraînés par la vague de parallélisation, sous l'impulsion des processeur multic\oe urs, on utilise celle-ci dans pour tous les calculs on son usage se justifie. On pourrait penser cette tâche compliquée, tant les constructeurs ont habituellement du mal à s'accorder sur des standards, mais \emph{OpenCL} s'impose pour quiconque veut faire un programme portable. On peut noter aussi l'existence de \emph{CUDA}, technologie propre à \emph{Nvidia}, qui permet d'effectuer à la même chose. Parmi les programmes répandus utilisant ce type de technologies, on peut noter le logiciel \emph{Photoshop}. En effet, lorsque l'on applique un filtre à une image composées de plusieurs millions de pixels, utiliser le processeur est dispendieux en temps. Par conséquence, \emph{CUDA} et \emph{OpenCL} sont utilisés, et accélèrent grandement la vitesse d'exécution.

Dans notre cas, ce bref aperçu de \emph{OpenCL} nous a permis de comprendre l'aspect technique qui se cache derrière, et de voir ce que cela apporte. Toutefois, il n'a pas été réalisé de test de performance formels, pour cause de mauvaise organisation. En effet, l'effort a été concentré sur la réalisation des objectifs fonctionnels, et il a manqué de temps pour effectuer des test en bonne et due forme. En outre, un problème majeur qui a été rencontré lors de ce projet, c'est qu'il ne nous a pas été possible d'avoir le même comportement sur les machines mises à disposition au CREMI, et nos machines personnelles, en dépit de l'utilisation de standards. Le code lié à la création des noyaux et du contexte d'exécution nous ayant été fourni pour gagner du temps, et ne voulant pas tout recommencer au risque de ne pas arriver à temps à obtenir ce que l'on souhaitait, a fait qu'il nous a fallu travailler sur la partie \emph{OpenCL} uniquement au CREMI, ce qui nous a fortement limité. Enfin, même si une fois compris le principe tout devient plus facile, il a fallu un certain temps avant qu'on arrive à une aisance dans la manipulation d'\emph{OpenCL}, de la carte graphique et des notions associées.
\end{document}
